#!/usr/bin/python
#
# exp.py - Classes to represent underlying data structures for the grammar
#	 below, for the mini-compiler.
#
# Kurt Schmidt
# 8/07
#
# Modified by Group 4
# 4-22-2011
#
# DESCRIPTION:
#		Just a translation of the C++ implementation by Jeremy Johnson (see
#		programext.cpp)
#
# EDITOR: cols=80, tabstop=2
#
# NOTES
#	environment:
#		a dict
#
#		Procedure calls get their own environment, can not modify enclosing env
#
#	Grammar:
#		program: stmt_list 
#		stmt_list:  stmt ';' stmt_list 
#		    |   stmt  
#		stmt:  assign_stmt 
#		    |  define_stmt 
#		    |  if_stmt 
#		    |  while_stmt 
#		assign_stmt: IDENT ASSIGNOP expr
#		define_stmt: DEFINE IDENT PROC '(' param_list ')' stmt_list END
#		if_stmt: IF expr THEN stmt_list ELSE stmt_list FI
#		while_stmt: WHILE expr DO stmt_list OD
#		param_list: IDENT ',' param_list 
#		    |      IDENT 
#		expr: expr '+' term   
#		    | expr '-' term   
#		    | term            
#		term: term '*' factor   
#		    | factor            
#		factor:     '(' expr ')'  
#		    |       NUMBER 
#		    |       IDENT 
#		    |       funcall 
#		funcall:  IDENT '(' expr_list ')'
#		expr_list: expr ',' expr_list 
#		    |      expr 
#
#      We added new Grammars:
#		list : LBRACKET seq_list RBRACKET
#		    | LBRACKET RBRACKET
#		seq_list : list COMMA seq_list
#              	    | list
#              	    | expr 
#		    | expr COMMA seq_list
#
#		assign_stmt : IDENT ASSIGNOP expr
#		    | IDENT ASSIGNOP list
#		    | IDENT ASSIGNOP concat
#
#		fact : cons'
#		fact : car
#		fact : cdr'
#		fact : nullp
#		fact : listp'
#		fact : intp'
#
#		cons : CONS LPAREN expr COMMA expr RPAREN
#		    | CONS LPAREN expr COMMA list RPAREN
#		    | CONS LPAREN list COMMA expr RPAREN
#		    | CONS LPAREN list COMMA list RPAREN
#		car : CAR LPAREN list RPAREN
#		    | CAR LPAREN fact RPAREN
#		cdr : CDR LPAREN expr RPAREN
#		    | CDR LPAREN list RPAREN
#		nullp : NULLP LPAREN list RPAREN
#		    | NULLP LPAREN fact RPAREN
#		listp : LISTP LPAREN list RPAREN
#		    | LISTP LPAREN fact RPAREN
#		intp : INTP LPAREN list RPAREN
#		    | INTP LPAREN fact RPAREN
#
#		concat : expr CONCAT expr
#		    | list CONCAT list
#
#

from MiniHeap import *
import sys

####  CONSTANTS   ################

	# the variable name used to store a proc's return value
returnSymbol = 'return'

tabstop = '  ' # 2 spaces

######   NEW CLASSES/OBJECTS FOR ASSIGNMENT 3   ##################

		
# function for adding lists to memory
#def AllocateMemory(L,heap):
#	cdr_indx =-1
#	for e in reversed(L):
#                
#		consCell = heap.getConCell()
#		if consCell != None:
#
#			if type(e)==type(list()):
#				print 'type: List'
#				conList = AllocateMemory(e,heap)
#				#consCell = heap.getConCell()
#				consCell.conCar.listMark = True
#				consCell.conCdr.value = cdr_indx
#				consCell.conCdr.listMark = True
#
#			elif type(e)==type(ConCell(None,None,None)):
#				print 'type: ConCell'
#				consCell.conCar.value = e.pos
#				consCell.conCdr.listMark = True
#						
#			else:
#				#consCell = heap.getConCell()
#				consCell.conCar.value = e
#				consCell.conCdr.value = cdr_indx
#				consCell.conCdr.listMark = True
#			cdr_indx = consCell.pos
#			print consCell
#		else:
#			#throw error?
#			#or return a value that indicates memory not allocated
#			#may be break from the loop as well
#			consCells = None
               
			
#	print consCell	
#	return consCell

					
######   CLASSES   ##################

class Expr :
	'''Virtual base class for expressions in the language'''

	def __init__( self ) :
		raise NotImplementedError(
			'Expr: pure virtual base class.  Do not instantiate' )

	def eval( self, nt, ft ) :
		'''Given an environment and a function table, evaluates the expression,
		returns the value of the expression (an int in this grammar)'''

		raise NotImplementedError(
			'Expr.eval: virtual method.  Must be overridden.' )

	def display( self, nt, ft, depth=0 ) :
		'For debugging.'
		raise NotImplementedError(
			'Expr.display: virtual method.  Must be overridden.' )

class Sequence( Expr ) :

	def __init__(self, v) :
		self.v = v
		

	def __init__(self, v, l = None) :
		self.v = v
		self.l = l
		

	def eval(self, nt, ft) :
		return [self.v]


class Number( Expr ) :
	'''Just integers'''

	def __init__( self, v=0 ) :
		self.value = v
	
	def eval( self, nt, ft ) :
		return self.value

	def display( self, nt, ft, depth=0 ) :
		print "%s%i" % (tabstop*depth, self.value)
 
#### Class for List ####
  	
class List :
	'''Generic List of lists and numbers'''

	def __init__( self, v=0 ) :
		#self.v = v		
		values = []
		if v == None:
			print '$$$$$$$$$$$$$$$$'
		for le in v:
			values.append(le)
		self.value = values
	
	def eval( self, nt, ft ) :
		returnVal = []
		consCell = None
		#value = []
		# The if is to prevent trying to eval an empty list
		# which causes a can't eval type str error
		#seq = self.v.eval(nt,ft)		
		#for le in seq:
		#	value.append(le)
		
		#if type(selfvalue[0]) != type(str()):
		#	print 'List(): inside if'
		#	for element in value:
		#		returnVal.append(element)
		if type(self.value[0]) != type(str()):
			for element in self.value:
				returnVal.append(element)
			#to allocate memory for the list
			cdr=-1
			L = None
			for e in reversed(returnVal):
				#print 'List(): Inside for loop'
				cons = Cons(e,L)
				consCell = cons.eval(nt,ft)
				consCell.conCdr.value = cdr
				cdr = consCell.pos
				L = consCell
				#print consCell
		else:
			print '$$$$$$$$$'
			cons = Cons(None,None)
			consCell = cons.eval(nt,ft)
			print '$$$$$$$$$'
		if consCell != None :
			consCell.head = True
		
		return consCell  
		#return returnVal

	def display( self, nt, ft, depth=0 ) :
		print "%s%i" % (tabstop*depth, self.value)

#### class that implements the car function ####
		
class Car( List ) :
	'''Function for returning the head of a list'''

	def __init__( self, v=0 ) :
		self.value = v
	
	def eval( self, nt, ft ) :
		val = self.value.eval(nt, ft)
		if isinstance(val,ConCell):
			if val.conCar.listMark == True:
				val1 = heap[val.conCar.value]
				return str(val1)
				
			else:
				return val.conCar.value

	def display( self, nt, ft, depth=0 ) :
		print "%s%i" % (tabstop*depth, self.value)
      
#### Class to implement the nullp(l) function ####
		
class Nullp( List ) :
	'''Function for testing if a list is null'''

	def __init__( self, v=0 ) :
		self.value = v
	
	def eval( self, nt, ft ) :
		val = self.value.eval(nt, ft)
		if val == None or val.conCar.value == None :
			val = 1
		else :
			val = 0
		
		return val

	def display( self, nt, ft, depth=0 ) :
		print "%s%i" % (tabstop*depth, self.value)
		

#### Class to implement the listp(l) function ####
class Listp( List ) :
	'''Function for testing if the first element of a list is a list'''

	def __init__( self, v=0 ) :
		self.value = v
	
	def eval( self, nt, ft ) :
		val = self.value.eval(nt, ft)
		if isinstance(val,ConCell):
			val = 1
		#if type(val) == type(list()):
		#	val = 1
		else :
			val = 0
		return val

	def display( self, nt, ft, depth=0 ) :
		print "%s%i" % (tabstop*depth, self.value)


#### Class to implement the intp(e) function ####
class Intp( List ) :
	'''Function for testing if the value is an integer'''

	def __init__( self, v=0 ) :
		self.value = v
	
	def eval( self, nt, ft ) :
		val = self.value.eval(nt, ft)
		if type(val) == type(int()):
			val = 1
		else :
			val = 0
		return val

	def display( self, nt, ft, depth=0 ) :
		if type(self.value) == type(int()):
			print "%s%d" % (tabstop*depth, self.value)


#### Class to implement the cons(e,L) funcion ####
class Cons( List ) :
	'''Funtion to add an element to the head of the list'''

	def __init__(self, el, L ) :
		self.el = el
		self.L = L

	def eval( self, nt, ft ) :
		if self.L == None or type(self.L)==type(ConCell(None,None,None)):
			#print 'Cons: inside the if of if self.L == None or type(self.L)==type(ConCell(None,None,None)):'
			l = self.L
			
		else: 
			#print 'Cons: inside else of if self.L == None or type(self.L)==type(ConCell(None,None,None))'
			l = self.L.eval( nt, ft )
			
		if self.el == None:
			e = self.el
		elif isinstance(self.el, ConCell) :
			e = self.el
		else:
			e = self.el.eval( nt, ft )
		#print l.__class__
		
			# testing a new approach:
		consCell = heap.getConCell()
		if consCell == None:
			print 'Out of Memory'
		else:
			#print 'Cons: inside else of None check'
			#if (isinstance(l,Ident) and l.eval(nt,ft)==None) or l==None:
			#if isinstance(l,Ident) and l.eval(nt,ft)==None:
			if l==None:	
				print 'Cons: inside type None'
				#if type(e) == type(ConCell(None,None,None)):
				if isinstance(e,ConCell):	
					consCell.conCar.value = e.pos
					consCell.conCar.listMark = True
					
					#consCell.conCdr.value = -1
				else:
					consCell.conCar.value = e
					
				consCell.conCdr.value = -1
			elif (isinstance(l,Ident) and isinstance(l.eval(nt,ft),ConCell)) or isinstance(l,List):
				print '*************************************'
				lt = self.L.eval(nt,ft)
				lt.head = False
				#if type(e) == type(ConCell(None,None,None)):
				
				if isinstance(e,ConCell):
					consCell.conCar.value = e.pos
					consCell.conCar.listMark = True
					
					#consCell.conCar.value = e.pos
					#consCell.conCar.listMark = True
					#consCell.conCdr = l.pos
				else:
					consCell.conCar.value = e
				# added this check so if L is an empty list in cons(e,L)
				# the new list created does not point its cdr to the empty list, but is -1
				if lt.conCar.value == None:
					print '@@@@@@@@@@@@@@@@@@@@@@'
					consCell.head = True
					consCell.conCdr.value = -1
				else:
					consCell.head = True
					consCell.conCdr.value = lt.pos
				#consCell.head = True
				#consCell.conCdr.value = lt.pos
			#elif isinstance(l,List):
			#	print '#################################'
			#	lt = self.L.eval(nt,ft)
			#	if type(e) == type(ConCell(None,None,None)):
			#		consCell.conCar.value = e.pos
			#		consCell.conCar.listMark = True
			#		#consCell.conCdr = l.pos
			#	else:
			#		consCell.conCar.value = e
			#	
			#	consCell.conCdr.value = lt.pos

			#elif type(l) == type(ConCell(None,None,None)):
			elif isinstance(l,ConCell):
				#print 'Cons: inside type ConCell'
				#if type(e) == type(ConCell(None,None,None)):
				if isinstance(e,ConCell):
					consCell.conCar.value = e.pos
					consCell.conCar.listMark = True
					
					
					#consCell.conCdr = l.pos
				else:
					consCell.conCar.value = e
				
				if consCell.pos != l.pos :
					consCell.conCdr.value = l.pos
			
			else:
				print l,':is not a list in the Minilangage'
				sys.exit(2)
		
		return consCell		
		#return l
		
	def display( self, nt, ft, depth=0 ):
		print "%sCONS" % (tabstop*depth)
		self.el.display( nt, ft, depth+1 )
		self.L.display( nt, ft, depth+1 )


#### Class to implement the cdr(L) function ###
class Cdr( List ) :
	'''Function to return the list minus the first element'''

	def __init__(self, L ) :
		self.L = L

	def eval( self, nt, ft ) :
		l = self.L.eval( nt, ft )
		if type(l) == type(list()) or type(l)==type(ConCell(None,None,None)):
			#newList = l[1:]
			pos = l.conCdr.value
			consCell = heap.lHeap[pos]
			if consCell == None:
				print 'Out of Memory'
				sys.exit(2)

			return consCell
		else:
			print l, ' is not a list, cdr(list)'
			sys.exit( 1 )

	def display( self, nt, ft, depth=0 ):
		print "%sCDR" % (tabstop*depth)
		self.L.display( nt, ft, depth+1 )


#### Class to implement the concatenation '||' operator ####
class Concat( Expr ) :
	'''expression for list concatenation'''

	def __init__( self, lhs, rhs ) :
		self.lhs = lhs
		self.rhs = rhs

	def eval( self, nt, ft ):
		l = self.lhs.eval( nt, ft )
		r = self.rhs.eval( nt, ft )
		returnList = []
		
		if l.__class__ == ConCell(None, None, None).__class__:
			end = 0			
			while end == 0 :
				index = l.conCdr.value
				if l.conCar.listMark : 
					returnList.append(heap.lHeap[l.conCar.value])
				else :
					returnList.append(Number(l.conCar.value))
				if index == -1 :
					end = 1
				else :
					l = heap.lHeap[index]
		else:
			print l, ' is not a valid list: list || list'
			sys.exit( 2 )
		if r.__class__ == ConCell(None, None, None).__class__:
			end = 0			
			while end == 0 :
				index = r.conCdr.value
				if r.conCar.listMark : 
					returnList.append(heap.lHeap[r.conCar.value])
				else :
					returnList.append(Number(r.conCar.value))
				if index == -1 :
					end = 1
				else :
					r = heap.lHeap[index]
		else:
			print r, ' is not a valid list: list || list'
			sys.exit( 2 )
		newList = List(returnList)
		return newList.eval(nt, ft)

	def display( self, nt, ft, depth=0 ) :
		print "%sCONCAT" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )


class Ident( Expr ) :
	'''Stores the symbol'''

	def __init__( self, name ) :
		self.name = name
	
	def eval( self, nt, ft ) :
		return nt[ self.name ]

	def display( self, nt, ft, depth=0 ) :
		print "%s%s" % (tabstop*depth, self.name)


class Times( Expr ) :
	'''expression for binary multiplication'''

	def __init__( self, lhs, rhs ) :
		'''lhs, rhs are Expr's, the operands'''

		# test type here?
		# if type( lhs ) == type( Expr ) :
		self.lhs = lhs
		self.rhs = rhs
	
	# add type checking to make sure * does not apply to list
	def eval( self, nt, ft ) :
		l = self.lhs.eval( nt, ft )
		r = self.rhs.eval( nt, ft )
		if type(l) != type(int()):
			print "left operand of the Times operation is not an int"
			sys.exit(1)
		if type(r) != type(int()):
			print "right operand of the Times operation is not an int"
			sys.exit(1)
		return l * r

	def display( self, nt, ft, depth=0 ) :
		print "%sMULT" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class Plus( Expr ) :
	'''expression for binary addition'''

	def __init__( self, lhs, rhs ) :
		self.lhs = lhs
		self.rhs = rhs
	
	# added type checking to make sure + does not apply to list
	def eval( self, nt, ft ) :
		l = self.lhs.eval( nt, ft )
		r = self.rhs.eval( nt, ft )
		if type(l) != type(int()):
			print "left operand of the plus operation is not an int"
			sys.exit(1)
		if type(r) != type(int()):
			print "right operand of the plus operation is not an int"
			sys.exit(1)
		return l + r

	def display( self, nt, ft, depth=0 ) :
		print "%sADD" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class Minus( Expr ) :
	'''expression for binary subtraction'''

	def __init__( self, lhs, rhs ) :
		self.lhs = lhs
		self.rhs = rhs
	
	# added type checking to make sure - does not apply to list
	def eval( self, nt, ft ) :
		l = self.lhs.eval( nt, ft )
		r = self.rhs.eval( nt, ft )
		if type(l) != type(int()):
			print "left operand of the minus operation is not an int"
			sys.exit(1)
		if type(r) != type(int()):
			print "right operand of the minus operation is not an int"
			sys.exit(1)
		return l - r

	def display( self, nt, ft, depth=0 ) :
		print "%sSUB" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class FunCall( Expr ) :
	'''stores a function call:
	  - its name, and arguments'''
	
	def __init__( self, name, argList ) :
		self.name = name
		self.argList = argList
	
	def eval( self, nt, ft ) :
		return ft[ self.name ].apply( nt, ft, self.argList )

	def display( self, nt, ft, depth=0 ) :
		print "%sFunction Call: %s, args:" % (tabstop*depth, self.name)
		for e in self.argList :
			e.display( nt, ft, depth+1 )


#-------------------------------------------------------

class Stmt :
	'''Virtual base class for statements in the language'''

	def __init__( self ) :
		raise NotImplementedError(
			'Stmt: pure virtual base class.  Do not instantiate' )

	def eval( self, nt, ft ) :
		'''Given an environment and a function table, evaluates the expression,
		returns the value of the expression (an int in this grammar)'''

		raise NotImplementedError(
			'Stmt.eval: virtual method.  Must be overridden.' )

	def display( self, nt, ft, depth=0 ) :
		'For debugging.'
		raise NotImplementedError(
			'Stmt.display: virtual method.  Must be overridden.' )


class AssignStmt( Stmt ) :
	'''adds/modifies symbol in the current context'''

	def __init__( self, name, rhs ) :
		'''stores the symbol for the l-val, and the expressions which is the
		rhs'''
		self.name = name
		self.rhs = rhs
	
	def eval( self, nt, ft ) :
		nt[ self.name ] = self.rhs.eval( nt, ft )

	def display( self, nt, ft, depth=0 ) :
		print "%sAssign: %s :=" % (tabstop*depth, self.name)
		self.rhs.display( nt, ft, depth+1 )


class DefineStmt( Stmt ) :
	'''Binds a proc object to a name'''

	def __init__( self, name, proc ) :
		self.name = name
		self.proc = proc

	def eval( self, nt, ft ) :
		ft[ self.name ] = self.proc

	def display( self, nt, ft, depth=0 ) :
		print "%sDEFINE %s :" % (tabstop*depth, self.name)
		self.proc.display( nt, ft, depth+1 )


class IfStmt( Stmt ) :


	def __init__( self, cond, tBody, fBody ) :
		'''expects:
		cond - expression (integer)
		tBody - StmtList
		fBody - StmtList'''
		
		self.cond = cond
		self.tBody = tBody
		self.fBody = fBody

	def eval( self, nt, ft ) :
		if self.cond.eval( nt, ft ) > 0 :
			self.tBody.eval( nt, ft )
		else :
			self.fBody.eval( nt, ft )

	def display( self, nt, ft, depth=0 ) :
		print "%sIF" % (tabstop*depth)
		self.cond.display( nt, ft, depth+1 )
		print "%sTHEN" % (tabstop*depth)
		self.tBody.display( nt, ft, depth+1 )
		print "%sELSE" % (tabstop*depth)
		self.fBody.display( nt, ft, depth+1 )


class WhileStmt( Stmt ) :

	def __init__( self, cond, body ) :
		self.cond = cond
		self.body = body

	def eval( self, nt, ft ) :
		while self.cond.eval( nt, ft ) > 0 :
			self.body.eval( nt, ft )

	def display( self, nt, ft, depth=0 ) :
		print "%sWHILE" % (tabstop*depth)
		self.cond.display( nt, ft, depth+1 )
		print "%sDO" % (tabstop*depth)
		self.body.display( nt, ft, depth+1 )

#-------------------------------------------------------

class StmtList :
	'''builds/stores a list of Stmts'''

	def __init__( self ) :
		self.sl = []
	
	def insert( self, stmt ) :
		self.sl.insert( 0, stmt )
	
	def eval( self, nt, ft ) :
		for s in self.sl :
			s.eval( nt, ft )
	
	def display( self, nt, ft, depth=0 ) :
		print "%sSTMT LIST" % (tabstop*depth)
		for s in self.sl :
			s.display( nt, ft, depth+1 )


class Proc :
	'''stores a procedure (formal params, and the body)

	Note that, while each function gets its own environment, we decided not to
	allow side-effects, so, no access to any outer contexts.  Thus, nesting
	functions is legal, but no different than defining them all in the global
	environment.  Further, all calls are handled the same way, regardless of
	the calling environment (after the actual args are evaluated); the proc
	doesn't need/want/get an outside environment.'''

	def __init__( self, paramList, body ) :
		'''expects a list of formal parameters (variables, as strings), and a
		StmtList'''

		self.parList = paramList
		self.body = body

	def apply( self, nt, ft, args ) :
		newContext = {}

		# sanity check, # of args
		if len( args ) is not len( self.parList ) :
			print "Param count does not match:"
			sys.exit( 1 )

		# bind parameters in new name table (the only things there right now)
			# use zip, bastard
		for i in range( len( args )) :
			newContext[ self.parList[i] ] = args[i].eval( nt, ft )

		# evaluate the function body using the new name table and the old (only)
		# function table.  Note that the proc's return value is stored as
		# 'return in its nametable

		self.body.eval( newContext, ft )
		if newContext.has_key( returnSymbol ) :
			return newContext[ returnSymbol ]
		else :
			print "Error:  no return value"
			sys.exit( 2 )
	
	def display( self, nt, ft, depth=0 ) :
		print "%sPROC %s :" % (tabstop*depth, str(self.parList))
		self.body.display( nt, ft, depth+1 )


class Program :
	
	def __init__( self, stmtList ) :
		self.stmtList = stmtList
		self.nameTable = {}
		self.funcTable = {}
		heap.setNameTable(self.nameTable)
	
	def eval( self ) :
		self.stmtList.eval( self.nameTable, self.funcTable )
	
	def dump( self ) :
		print "Dump of Symbol Table"
		print "Name Table"
		for k in self.nameTable :
			print "  %s -> %s " % ( str(k), str(self.nameTable[k]) )
		print "Function Table"
		for k in self.funcTable :
			print "  %s" % str(k)

	def display( self, depth=0 ) :
		print "%sPROGRAM :" % (tabstop*depth)
		self.stmtList.display( self.nameTable, self.funcTable )


